1. Field of the Invention
The present invention relates to a data processing apparatus, a data processing method adopted by the data processing apparatus and a data processing program implementing the data processing method. In particular, the present invention relates to a data processing apparatus capable of inferring a data series by making use of a trellis with a high degree of precision while reducing the number of surviving states surviving in the trellis and relates to a data processing method adopted by the data processing apparatus as well as a data processing program implementing the data processing method.
2. Description of the Related Art
A convolution code is a typical example of codes used in a wide range of fields such as communications and broadcastings. The convolution code has a much peculiar feature of a capability of implementing a maximum-likelihood decoding process of decoding a code word into a most likely data series. A data series is an information series serving as a subject of a coding process. A Viterbi decoding method is a typical example of methods for implementing the maximum-likelihood decoding process.
In accordance with the Viterbi decoding method, a most likely data series is inferred by making use of a trellis (referred to as a maximum-likelihood inference process).
That is to say, in accordance with the Viterbi decoding method, a process to find a candidate for a path (a series of states) of a minimum distance (a minimum matrix) passing through states as a path for the states and store the candidate in a memory is carried out repeatedly so that, while wasteful computation processing is being eliminated, a received word and a code word of the minimum distance can be eventually selected.
The Viterbi decoding method has a feature that, if the decoding length (or the coding length) increases, the amount of processing increases only linearly.
In the ISDB (Integrated Services Digital Broadcasting)-T system or other systems, an OFDM (Orthogonal Frequency Division Multiplexing) technique is adopted. The ISDB-T system is one of ground wave digital television broadcasting systems in Japan.
The OFDM technique adds the rear portion of each symbol to the head (of the symbol) to serve as a guard interval so as to offer a characteristic of resistance against a delayed wave (or a multipath echo). If a delay exceeding the length of a guard interval exists, however, interferences between symbols and interferences between carriers are generated so that the signal reception characteristic (or the signal decoding characteristic) deteriorates considerably.
Even if a delayed wave exceeding the length of a guard interval exists, interferences between symbols can be reduced whereas interferences between carriers other than carriers adjacent to each other can also be decreased as well. The decrease can be implemented by typically applying a Hannington window to an OFDM signal of the base band and carrying out FFT (Fast Fourier Transform) processing.
Let reference notation n denote a carrier number used for identifying a carrier (or a sub-carrier) of an OFDM signal whereas reference notation Yn denote an OFDM signal obtained by applying a Hannington window to the OFDM signal and carrying out the FFT processing. In the following description, the OFDM signal obtained by applying a Hannington window to the OFDM signal and carrying out the FFT processing is referred to as a reduced-interference signal. In this case, the reduced-interference signal Yn is expressed by Eq. (1) as follows:[Eq. 1]Yn=−½Xn−1Hn−1+XnHn−½Xn+1Hn+1Nn  (1)
In the above equation, reference notation Xn denotes a transmitted symbol transmitted by making use of carrier #n which is a carrier identified by the carrier number n.
On the other hand, reference notation Nn denotes a noise component included in the reduced-interference signal Yn. The noise component Nn is the sum of interferences between symbols, interferences between carriers and an additivity white noise. In addition, reference notation Hn denotes the characteristic of a transmission line for carrier #n. In the following description, the characteristic of a transmission line is also referred to as transmission-line information.
It is to be noted that, in Eq. (1) given above, a coefficient of −½ multiplied by a term Xn−1Hn−1, a coefficient of +1 multiplied by a term XnHn and a coefficient of −½ multiplied by a term Xn+1Hn+1 are each a coefficient of the Hannington window.
Carrier #n, which is a carrier identified by the carrier number n, is the nth carrier among carriers arranged in an order of increasing carrier frequencies.
In accordance with Eq. (1), the reduced-interference signal Yn can be perceived as a convolution code obtained as a result of a convolution coding process by making use of two memories used for storing transmitted symbols Xn and Xn−1 as internal states. Thus, if the transmission-line information Hn is known and each of the transmitted symbols Xn transmitted by making use of carriers #n having carrier numbers n equal to or smaller than 0 is assumed to be 0, the transmitted symbols Xn can be inferred as a result of a process of inferring a series of transmitted symbols X0, X1 and so on by making use of a trellis. The series of transmitted symbols X0, X1 and so on is a series of aforementioned transmitted symbols Xn.
That is to say, the transmitted symbols Xn can be inferred by carrying out a maximum-likelihood inference process adopting typically the Viterbi decoding method.
In a Viterbi decoder for carrying out a maximum-likelihood inference process adopting the Viterbi decoding method on a transmitted symbol Xn, the number of trellis states is equal to the second power of a signal-point count which is the number of signal points of the first-order modulation of the OFDM signal. The signal points of the first-order modulation of the OFDM signal are signal points on an IQ-constellation plane.
The first-order modulation processing carried out in the ISDB-T system cited before is a 64QAM (Quadrature Amplitude Modulation) process, a 16QAM process, a QPSK (Quadrature Phase Shift Keying) process or a BPSK (Binary Phase Shift Keying) process.
If the 64QAM process is carried out as the first-order modulation processing for example, the number of trellis states is 4,096(=64×64).
In addition, in the Viterbi decoder, the number of branch metrics BM to be computed for one state of the trellis is equal to the signal-point count which is the number of signal points of the first-order modulation of the OFDM signal.
Since the number of trellis states is equal to the second power of a signal-point count which is the number of signal points of the first-order modulation of the OFDM signal as described above, the number of branch metrics BM to be computed for one carrier of the OFDM signal is the third power of the number of signal points of the first-order modulation of the OFDM signal.
FIG. 1 is a diagram showing a trellis of a general Viterbi decoding method.
It is to be noted that, in the trellis shown in the diagram of FIG. 1 or any of other figures in this patent specification, the axis stretched in the horizontal direction is a time axis representing the lapse of time. Each of circles arranged in the vertical direction represents a trellis state at a particular time. A segment connecting any two states of the trellis is referred to as a branch.
If the 64QAM process is carried out as the first-order modulation processing, the number of trellis states at a particular point of time is 4,096(=64×64) as described above. In addition, the number of branch metrics BM to be computed for each carrier of the OFDM signal is 262,144(=64×64×64). Thus, it is extremely difficult to implement a Viterbi decoder having a small size.
A method described in non-patent document 1 (mentioned later) is a typical method for reducing the increase of the size of a data-series inference detector for inferring a data series. The Viterbi detector is a typical example of the data-series inference detector. In the following description, the method described in non-patent document 1 is referred to as an M algorithm.
In accordance with the M algorithm, the number of surviving states surviving on the trellis is repressed as described below in order to reduce the increase of the size of a data-series inference detector. A surviving state surviving in the trellis is defined as a state stored in the data-series inference detector.
That is to say, in accordance with the M algorithm, at every time, the number of states originated from one surviving state is limited to a number M determined in advance as shown in the diagrams of FIGS. 2A to 2C. In the following description, a state originated from one surviving state through a branch is also referred to as a child state and a surviving state from which a child state is also referred to as a parent state. The number M determined in advance is referred to as a limited state count. Then, state metrics sm of child states originated from all surviving parent states are sorted. Subsequently, in accordance with the M algorithm, C child states are selected from the child states, the state metrics sm of which have been sorted, in an order of increasing state metrics to serve as new surviving states where reference notation C denotes an integer determined in advance. In other words, each of the C selected child states has a relatively small state metric sm in comparison with those of the unselected states. That is to say, the C child states are selected in an order of increasing state metrics sm starting with the smallest state metric among the sorted state metrics sm. Symbol C denotes a certain constant. These processes of limiting the number of child states to the limited state count M, sorting the state metrics sm of the child states and selecting new surviving states from the child states are carried out repeatedly.
Finally, in accordance with the M algorithm, a data series is inferred by going upstream through preceding surviving states from a determined surviving state.
FIGS. 2A to 2C are explanatory diagrams referred to in description of the M algorithm.
In case of the M algorithm explained by referring to the diagrams of FIGS. 2A to 2C, the limited state count M is set at 2 whereas the predetermined integer C representing the number of surviving states selected at the most recent time is set at 4. In the following description, the number of surviving states selected at the most recent time is referred to as a most recent surviving state count C.
FIG. 2A is a diagram showing a trellis to which the M algorithm is applied.
In the trellis shown in the diagram of FIG. 2A, for example, four surviving states exist at a time t of n (that is, for the time t=n). In the diagrams of FIGS. 2A to 2C, a white circle denotes a surviving state whereas a black circle denotes a state not selected to serve as a surviving state. In the following description, the phrase “for the time t=n” is also used to mean “at a time of n.”
In accordance with the M algorithm, child states are originated from each of the four surviving parent states existing for the time t=n to serve as child states for the time t=n+1. The number of child states is limited to the limited state count M which is set at 2 as described above.
That is to say, two (=M) child states originated from any specific one of the four surviving parent states, which exists for the time t=n, through branches to serve as child states for the time t=n+1 are found to serve as two child states, which have smallest branch metrics BM, among child states that can be originated from the specific parent state. The child states found in this way each serves as a candidate for a surviving state for the time t=n+1.
To put it concretely, in the trellis shown in the diagram of FIG. 2A, four surviving states exist for the time t=n. Since two child states originate from each of the four surviving parent states existing for the time t=n to serve as two child states for the time t=n+1, for the time t=n+1, eight child states each become a candidate for a surviving state for the time t=n+1.
Thereafter, the branch metric BM of each of the eight child states each becoming a candidate for a surviving state for the time t=n+1 is found and the branch metrics BM are then sorted.
Subsequently, four (=C) candidates for surviving states are selected in an order of increasing branch metrics BM from the eight candidates for the surviving states for the time t=n+1 to serve as new surviving states for the time t=n+1.
In the same way, two (=M) child states originated from any specific one of the four surviving parent states, which exist for the time t=n+1, through branches to serve as child states for the time t=n+2 are found as 2 child states, which have smallest branch metrics BM, among child states that can be originated from the specific parent state. The child states found in this way each serves as a candidate for a surviving state for the time t=n+2. Then, the subsequent processes described above are repeated.
Each of FIGS. 2B and 2C is a diagram showing surviving grandparent states which need to be stored in a memory in advance after the execution of the processing to select surviving states by adoption of the M algorithm as described above by referring to the diagram of FIG. 2A.
To be more specific, FIG. 2B is a diagram showing three grandparent states for the time t=n−1 as surviving states which need to be stored in a memory in advance after four surviving grandchild states have been selected for the time t=n+1 lagging behind time t=n−1 by a typical interval of two time units.
The three stored surviving states have been selected from grandparent states for the time t=n−1 as surviving states each linked to one of the four surviving grandchild states for the time t=n+1 by a branch and need to be stored in a memory in advance to be used for inferring a data series in a process of going upstream through preceding surviving states in the trellis. In the diagram of FIG. 2B, the three stored surviving states selected from grandparent states for the time t=n−1 are enclosed by a dotted line in order to indicate that the three selected surviving states are grandparent states which need to be stored in a memory in advance.
By the same token, FIG. 2C is a diagram showing four grandparent states for the time t=n as surviving states which need to be stored in a memory in advance after four surviving grandchild states have been selected for the time t=n+2 lagging behind time t=n by a typical interval of two time units.
In the same way, the four stored surviving states have been selected from grandparent states for the time t=n as surviving states each linked to one of the four surviving grandchild states for the time t=n+2 by a branch and need to be stored in a memory in advance to be used for inferring a data series in a process of going upstream through preceding surviving states in the trellis. In the diagram of FIG. 2C, the four stored surviving states selected from grandparent states for the time t=n are enclosed by a dotted line in order to indicate that the four selected surviving states are grandparent states which need to be stored in a memory in advance.
A document used in this patent specification as non-patent document 1 mentioned before is “Source and Channel Coding: An Algorithmic Approach,” J. B. Anderson and S. Mohan, Kluwer Academic Press, 1991.